package practice_2025_8_4;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

/**
 * 分割等和子集
 */
public class Main {
    // 36 - 46
    // 取出若干个数，取出和 = 剩下和
    // 1 5 5 11 -> 22
    // 1 1 2 3 5 -> 12
    // sum
    // 若和为偶数时
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        long sum = 0;
        for(int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
            sum += nums[i];
        }
        // 是否能均分
        if (sum % 2 != 0) {
            System.out.println("false");
        } else {
            // 排序
            Arrays.sort(nums);
            sum /= 2;
            long count = 0;
            boolean flg = false;
            for(int left = 0, right = 0; right < n; right++) {
                // 进窗口
                count += nums[right];
                // 判断更新
                if (count == sum) {
                    flg = true;
                    break;
                }
                // 出窗口
                while(count > sum && left < right) {
                    count -= nums[left];
                    left++;
                }
            }
            if (flg) {
                System.out.println("true");
            } else {
                System.out.println("false");
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
            sum += nums[i];
        }
        // 是否能均分
        if (sum % 2 != 0) {
            System.out.println("false");
        } else {
            // 01背包问题
            sum /= 2;
            boolean[][] dp = new boolean[n + 1][sum + 1];
            dp[0][0] = true;
            for(int i = 1; i <= n; i++) {
                for(int j = 0; j <= sum; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= nums[i - 1]) {
                        dp[i][j] = (dp[i][j]
                                || dp[i - 1][j - nums[i - 1]]);
                    }
                }
            }
            if (dp[n][sum]) {
                System.out.println("true");
            } else {
                System.out.println("false");
            }
        }
    }
}